Conventionally, parallel computers each including a plurality of nodes performing arithmetic processing are known. The nodes included in a parallel computer are interconnected through a network including a plurality of communication devices, routing devices (for example, switches), and the like and perform data communication with one another.
FIG. 34 is a diagram that illustrates an example of the configuration of a parallel computer 500.
The parallel computer 500 illustrated in FIG. 34 includes nodes N0 to N4 that perform computations and switches 510 to 514 that transmit received data to nodes of specific transmission destinations. The switches 510 to 514 configure a one-dimensional mesh-type network in which the switches are arranged on a straight line as a network topology.
When a switch receives a packet from an input port to which a node or another switch is connected, the above-described switch determines an output port to which a packet is output based on destination information included in the received packet. Then, the switch outputs the packet to the determined output port.
In addition, the switch includes a buffer 520 that temporarily stores received data or data to be output. In a case where an output contention occurs, the switch selects one packet, transmits the selected packet, and stores the other contending packets in the buffer 520.
In a case where a plurality of packets to be output to the same output port are received, the switch performs adjustment such that the numbers of packets to be output to the output port from input ports are uniform. Then, the switch transmits the packets from the output port in accordance with a result of the adjustment.
When packets exceeding the amount to be flown per unit time by the link are transmitted in the network, congestion occurs.
In the above-described parallel computer 500, when communication is concentrated on some switches, the communication bandwidth of a node decreases more as the number of hops of the node up to a switch on which communication is concentrated increases. In this case, the arrival of data at a destination node from a node having a large number of hops is delayed more than the arrival of data from a node having a small number of hops.
FIG. 35 is an exemplary diagram in which data is transmitted from the nodes N0 and N3 to the node N4.
Generally, a switch is adjusted such that packets from each input port are uniformly output. In other words, a switch adjusts packets to be input such that the numbers of packets output to output ports out of packets input to each input port are uniform, in other words, are respectively a half thereof. Accordingly, the number of packets that are transmitted from the node N3 to the switch 513 and are transmitted from the switch 513 to the switch 514 is a half of the number of all the packets transmitted from the switch 513 to the switch 514.
In the example illustrated in FIG. 35, in a route from the switch 513 to the node N4, packets transmitted from the node N0 and packets transmitted from the node N3 overlap each other, and communication bands for using the nodes N0 and N3 respectively become a half. However, since the nodes N0 and N3 continuously output packets in a maximum band, the buffer 520 is in a full (buffer-full) state. Hereinafter, the buffer-full state may be represented as the buffer 520 being full.
In a case where the being full of the buffer 520 occurs, for example, according to a communication control technique in which a packet is transmitted after a notification of vacancy of the buffer 520 of the transmission destination is received, there is a delay due to the notification. On the other hand, according to a communication control technique in which a packet is transmitted without checking the vacancy of the buffer 520 of the transmission destination, since a packet is discarded in a case where the buffer 520 of the transmission destination is in the full state, there is a need for retransmitting the packet. In other words, the communication performance is degraded in accordance with the delay caused by such a notification or packet retransmission.
In addition, the communication of the other nodes is influenced by the being full of the buffer 520. For example, in a case where buffers 520 of the switches 511 and 512 are full, it is necessary for communication between nodes N1 and N2 to be in a standby state until there is a vacancy in the buffer 520. In other words, the congestion propagates.
Here, a transmission method has been known in which a special gap packet is put between packets, the number of packets is adjusted based on the gap packet that has been put, and accordingly, discard of data and retransmission of data are suppressed.